# 链表 LinkedList
"""
链表通过“指针”将一组零散的内存块串联起来使用.其中，我们把内存块称为链表的“结点”。
为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址.

单链表、双向链表和循环链表。
1.单链表的尾结点指针指向空地址，表示这就是最后的结点了。
2.循环链表的尾结点指针是指向链表的头结点。循环链表是一种特殊的单链表。
3.双向链表，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。
"""


class Node(object):
    def __init__(self, value, next_node=None):
        self.data = value
        self.next = next_node


class SinglyLinkedList(object):
    def __init__(self):
        self.head = None

    def find_by_index(self, index: int) -> Node:
        p = self.head
        i = 0
        while p and i != index:
            p = p.next
            i += 1
        if not p:
            raise Exception('超出链表长度')
        return p

    def find_by_value(self, value) -> Node:
        if not self.head or not value:
            raise Exception('链表为空或查询值为空')
        p = self.head
        while p and p.data != value:
            p = p.next
        if not p:
            raise Exception('链表不存在查询值')
        return p

    def find_mid_node(self):
        """查找链表中的中间节点.
            主体思想:
                设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间节点
            返回:
                node:链表的中间节点
        """
        fast = self.head
        slow = self.head
        while fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def insert_node_to_head(self, new_node: Node) -> bool:
        if not new_node:
            raise Exception('新节点不能为空')
        new_node.next = self.head
        self.head = new_node
        return True

    def insert_value_to_head(self, value) -> bool:
        if value is None:
            raise Exception('值不能为空')
        new_node = Node(value)
        return self.insert_node_to_head(new_node)

    def insert_node_after(self, node: Node, new_node: Node) -> bool:
        if not self.head or not node or not new_node:
            raise Exception('链表为空或节点为空')
        p = self.head
        while p and p.next != node:
            p = p.next
        if not p:
            raise Exception('节点不存在链表中')
        new_node.next = node.next
        node.next = new_node
        return True

    def insert_value_after(self, node: Node, value) -> bool:
        new_node = Node(value)
        return self.insert_node_after(node, new_node)

    def insert_node_before(self, node: Node, new_node: Node) -> bool:
        if not node or not new_node:
            raise Exception('链表为空或节点为空')
        p = self.head
        while p.next and p.next != node:
            p = p.next
        if not p.next:
            raise Exception('节点不存在链表中')
        new_node.next = node
        p.next = new_node
        return True

    def insert_value_before(self, node: Node, value) -> bool:
        new_node = Node(value)
        return self.insert_node_before(node, new_node)

    def update_by_node(self, node: Node, new_node: Node) -> bool:
        if not node or not new_node:
            raise Exception('链表为空或节点为空')
        p = self.head
        while p.next and p.next != node:
            p = p.next
        if not p.next:
            raise Exception('节点不存在链表中')
        new_node.next = node.next
        p.next = new_node
        return True

    def update_by_value(self, node: Node, value) -> bool:
        new_node = Node(value)
        return self.update_by_node(node, new_node)

    def delete_by_node(self, node: Node) -> bool:
        if not node:
            raise Exception('节点为空')
        if self.head == node:
            self.head = self.head.next
            return True
        p = self.head
        while p and p.next != node:
            p = p.next
        if not p:
            raise Exception('节点不存在链表中')
        p.next = node.next.next
        return True

    def delete_by_value(self, value) -> bool:
        if not value:
            raise Exception('值为空')
        if self.head.data == value:
            self.head = self.head.next
            return True
        p = self.head
        while p and p.next.data != value:
            p = p.next
        if not p:
            raise Exception('值不存在链表中')
        p.next = p.next.next
        return True

    def delete_last_n_node(self, n):
        """删除链表中倒数第N个节点.
        主体思路：
            设置快、慢两个指针，快指针先行，慢指针不动；当快指针跨了N步以后，快、慢指针同时往链表尾部移动，
            当快指针到达链表尾部的时候，慢指针所指向的就是链表的倒数第N个节点
        参数:
            n:需要删除的倒数第N个序数
        """
        fast = self.head
        slow = self.head
        step = 1

        # 快指针跨了N步
        while step != n:
            fast = fast.next
            step += 1
        # 快、慢指针同时往链表尾部移动
        tmp = None
        while fast.next is not None:  # 快指针走向链表尾部时停止
            tmp = slow
            fast = fast.next
            slow = slow.next
        tmp.next = slow.next
        return True

    def reversed_self(self):
        if self.head is None or self.head.next is None:
            return
        pre = self.head
        node = self.head.next
        while node is not None:
            """
            创建一个前节点指针，当前节点的后节点指向前节点，当前节点，前节点 = 后节点， 当前节点
            linked_list = 4->3->2->1->0
            pre = (4)->3
            node = (3)->2
            交换：
                tmp = (2)->1  # tmp = node.next
                node = (3)->4  # node.next = pre
                pre = (3)->4  # pre = node
                node = (2)->1  # node = tmp
            """
            tmp = node.next
            node.next = pre
            pre = node
            node = tmp
        self.head.next = None
        self.head = pre
        return

    def has_ring(self):
        """检查链表中是否有环.
        主体思想：
            设置快、慢两种指针，快指针每次跨两步，慢指针每次跨一步，如果快指针没有与慢指针相遇而是顺利到达链表尾部
            说明没有环；否则，存在环
        返回:
            True:有环
            False:没有环
        """
        fast = self.head
        slow = self.head
        while fast and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

    def __repr__(self):
        result = []
        p = self.head
        while p:
            result.append(str(p.data))
            p = p.next
        return '->'.join(result)


class DbWayNode:
    def __init__(self, value, pre_node=None, next_node=None):
        self.data = value
        self.pre = pre_node
        self.next = next_node


class DbWayLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def find_by_index(self, index: int) -> DbWayNode:
        p = self.head
        i = 0
        while p and i != index:
            p = p.next
            i += 1
        if not p:
            raise Exception('超出链表长度')
        return p

    def find_by_value(self, value) -> DbWayNode:
        if not self.head or not value:
            raise Exception('链表为空或查询值为空')
        p = self.head
        while p and p.data != value:
            p = p.next
        if not p:
            raise Exception('链表不存在查询值')
        return p

    def find_mid_node(self) -> DbWayNode:
        fast = self.head
        slow = self.head
        while fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

    def append(self, value) -> bool:
        """
                添加节点的时候，我们首先要判断链表是否为空，另外要注意给原本的尾节点设置next属性，新的尾节点设置prev属性，更新链表的tail
                :param node:
                :return:
                """
        new_node = DbWayNode(value)
        if self.length == 0:
            self.head = new_node
            self.tail = self.head
            self.length = 1
            return True
        self.tail.next = new_node
        new_node.pre = self.tail
        self.tail = new_node
        self.length += 1
        return True

    def insert(self, index, value) -> bool:
        new_node = DbWayNode(value)
        if index < 0 and abs(index) >= self.length:
            index = 0
        elif index < 0:
            index = index + self.length
        if index == 0:
            if self.head != None:
                new_node.next = self.head
                self.head.pre = new_node
            else:
                self.tail = new_node
            self.head = new_node
            self.length += 1
            return True
        elif index >= self.length:
            self.append(value)
        else:
            node = self.find_by_index(index)
            new_node.next = node or None
            node.pre.next = new_node
            node.pre = new_node
        self.length += 1

        return True

    def update_by_node(self, node: DbWayNode, new_node: DbWayNode) -> bool:
        if not node or not new_node:
            raise Exception('链表为空或节点为空')
        p = self.head
        while p.next and p.next != node:
            p = p.next
        if not p.next:
            raise Exception('节点不存在链表中')
        new_node.next = node.next
        new_node.pre = node.pre
        new_node.next.pre = new_node
        p.next = new_node
        return True

    def update_by_value(self, node: DbWayNode, value) -> bool:
        new_node = DbWayNode(value)
        return self.update_by_node(node, new_node)

    def delete_by_node(self, node: DbWayNode) -> bool:
        if not node:
            raise Exception('节点为空')
        if self.head == node:
            self.head = self.head.next
            self.head.pre = None
            return True
        p = self.head
        while p and p.next != node:
            p = p.next
        if not p:
            raise Exception('节点不存在链表中')
        p.next = node.next.next
        p.next.pre = p
        return True

    def delete_by_value(self, value) -> bool:
        if not value:
            raise Exception('值为空')
        if self.head.data == value:
            self.head = self.head.next
            return True
        p = self.head
        while p and p.next.data != value:
            p = p.next
        if not p:
            raise Exception('值不存在链表中')
        p.next = p.next.next
        p.next.pre = p
        return True

    def reversed_self(self):
        if self.length <= 1:
            return
        node = self.head
        while node is not None:
            node.pre, node.next = node.next, node.pre
            node = node.pre
        return

    def __repr__(self):
        result = []
        p = self.head
        while p is not None:
            result.append(str(p.data))
            p = p.next
        return '->'.join(result)


if __name__ == '__main__':
    singly_linked_list = SinglyLinkedList()
    for i in range(10):
        singly_linked_list.insert_value_to_head(i)
    print(singly_linked_list)
    singly_linked_list.delete_last_n_node(2)
    print(singly_linked_list)
    singly_linked_list.delete_by_value(5)
    print(singly_linked_list)
    singly_linked_list.insert_value_to_head(10)
    print(singly_linked_list)
    print(singly_linked_list.head.data)
    singly_linked_list.insert_node_before(singly_linked_list.find_by_index(5), Node(5))
    print(singly_linked_list)
    singly_linked_list.insert_node_before(singly_linked_list.find_by_index(9), Node(1))
    print(singly_linked_list)
    print(singly_linked_list.find_mid_node().data)
    singly_linked_list.reversed_self()
    print(singly_linked_list)

    db_way_linked_list = DbWayLinkedList()
    for v in range(10):
        db_way_linked_list.append(v)
    print(db_way_linked_list)
    pass
